//Accepted
#include <cstdio>
#include <cmath>

int t, i, z, s;
bool no;
long long a, b, c, r, dd[10000];

int gcd(long long u, long long v){
	if(v>u){
		r=u;
		u=v;
		v=r;
	}
	while(1){
		if(v){
			r=u%v;
			u=v;
			v=r;
		}
		else return u;
	}
}

int main(){
	//freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
	scanf("%d", &t);
	while(t--){
		scanf("%d%d", &a, &c);
		if(c%a || c<a )printf("NO SOLUTION\n");
		else{
			for(i=1, z=0, s=(int)sqrt(c)+1 ; i<s ; ++i){
				if(c%i == 0){
					dd[z++]= i;
					dd[z++]= c/i;
				}
			}
			no=1;
			for(i=0;i<z && no;i+=2){
				b=dd[i];
				r = gcd(a,b);
				if((a*b)%r == 0){
					if( (a*b)/r == c){
						no=0;
					}
				}
			}
			for(--i;i>0 && no;i-=2){
				b=dd[i];
				r = gcd(a,b);
				if((a*b)%r == 0){
					if( (a*b)/r == c){
						no=0;
					}
				}
			}
			if(no)printf("NO SOLUTION\n");
			else printf("%d\n", b);
		}
	}
	return 0;
}
